package oj;


public class Day29F {
    public int getFirstUnFormedNum(int[] arr) {
        /**
         * 动态规划 01背包问题
         */
        int min=Integer.MAX_VALUE;
        int max=0;
        for(int a:arr){
            min=Math.min(a,min);
            max+=a;
        }
        boolean[] ret=new boolean[max+1];
        ret[0]=true;
        for(int a :arr){
            for(int j=max;j>=a;j--){
                ret[j]=ret[j-a]||ret[j];
            }
        }
        for(int j=min;j<ret.length;j++){
            if(!ret[j]){
                return j;
            }
        }
        return max+1;
    }
}


//        int max=0;
//        int min=Integer.MAX_VALUE;
//        HashSet<Integer> set=new HashSet<>();
//        for(int i=0;i<arr.length;i++){
//            min=Math.min(min,arr[i]);
//            max+=arr[i];
//        }
//        process(arr,0,0,set);
//        for(int i=min;i<=max;i++){
//            if(!set.contains(i)){
//                return i;
//
//            }
//        }
//        return max+1;
//    }
//    public static void process(int[] arr,int i,int preSum,HashSet<Integer> set) {
//        //决策结束，把决策累加的和加入set中
//        if (i == arr.length) {
//            set.add(preSum);
//            return;
//        }
//        //不要当前元素
//        process(arr,i+1,preSum,set);
//        //要当前元素
//        process(arr,i+1,preSum + arr[i],set);
//    }
//}